package jianzhi_offer;

public class _35_两个链表的第一个公共结点 {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1 = 0,len2 = 0;
        ListNode run = pHead1;
        while(run != null){
            ++len1;
            run = run.next;
        }
        run = pHead2;
        while(run != null){
            ++len2;
            run = run.next;
        }
        //保证第一个链表比第二个链表长
        if(len1 == len2){
            ListNode run1 = pHead1;
            ListNode run2 = pHead2;
            while(run1 != null && run2 != null){
                if(run1 == run2){
                    return run1;
                }
                run1 = run1.next;
                run2 = run2.next;
            }
            return null;
        }else{
            //这步可以省略
            int dis = len1-len2;
            if(len1 < len2){
                run = pHead1;
                pHead1 = pHead2;
                pHead2 = run;
                dis = len2-len1;
            }
            //开始找出一样的
            ListNode run1 = pHead1;
            while(dis>0){
                run1 = run1.next;
                --dis;
            }
            ListNode run2 =pHead2;
            while (run1 != null && run2 != null){
                if(run1 == run2){
                    return run1;
                }
                run1 = run1.next;
                run2 = run2.next;
            }
        }
        return null;
    }
}
